



// 数组中“存在”重复元素，且两个重复元素间的索引的差值<=k

// 1. 排序
typedef struct info {
    int idx;
    int num;
} info_t;

int cmp1(const void *a, const void *b) { // 传入&infos[i]
    return (*(info_t *)a).num - (*(info_t *)b).num;
}

// 数组中相同元素的索引的最小差值<=k
bool containsNearbyDuplicate(int* nums, int numsSize, int k){
    info_t infos[numsSize];
    for (int i = 0; i < numsSize; i++) {
        infos[i].idx = i;
        infos[i].num = nums[i];
    }
    qsort(infos, numsSize, sizeof(info_t), cmp1);

    for (int i = 0; i < numsSize-1; i++) {
        while (i < numsSize-1 && infos[i].num == infos[i+1].num) {
            if (infos[i+1].idx - infos[i].idx <= k) 
                return true;    // 满足存在条件
            i++; 
        }
    }

    return false;   
}


// 2. 哈希
// typedef struct info {
//     int key;
//     int idx;
//     UT_hash_handle hh;
// } uthash_t;

// bool containsNearbyDuplicate(int* nums, int numsSize, int k){
//     uthash_t *hash = NULL, *ret;
//     int is_exist = 0;
//     for (int i = 0; i < numsSize; i++) {
//         HASH_FIND_INT(hash, &nums[i], ret);
//         if (ret == NULL) {
//             uthash_t *tmp = malloc(sizeof(*tmp));
//             tmp->key = nums[i];
//             tmp->idx = i;
//             HASH_ADD_INT(hash, key, tmp);
//         } else {
//             if (i - ret->idx <= k) {
//                 is_exist = 1;
//                 break;
//             }
//             else ret->idx = i;
//         }
//     }

//     uthash_t *next, *del = NULL;
//     HASH_ITER(hh, hash, del, next) {
//         HASH_DEL(hash, del);
//         free(del);
//     }
//     return is_exist;   
// }